package com.zk.algorithm.greedy;

import com.zk.algorithm.Utils;
import com.zk.algorithm.bean.Interval;

/**
 * 圆周上 N 个区间，从中选出尽可能多的不想交的区间，一周被划分为 M 个区间
 *
 * @author zk
 */
public class WatchTVInCircle {

    public static void main(String...args) {
        Utils.println(new WatchTVInCircle().mostWatchNums(new Interval[]{
                new Interval(0, 5),
                new Interval(2, 7),
                new Interval(6, 8),
                new Interval(9, 1)
        }, 10));
    }

    /**
     *
     * @param intervals
     * @param M
     * @return
     */
    public int mostWatchNums(Interval[] intervals, int M) {
        WatchTV watchTV = new WatchTV();

        Interval[] circleIntervals = copyAndAppend(intervals, M);
        watchTV.sort(circleIntervals);

        int N = intervals.length;
        int res = 0;

        for (int i = 0; i < N; i++) {

            // =======================
            // 贪心法
            // =======================

            int ans = 0;
            int lastEnd = 0; // 最后所选工作的结束时间
            int maximumEnd = circleIntervals[i].start + M; // 从 circleIntervals[i] 节目开始看，最晚结束时间不能大于 maximumEnd

            // ==============================================================
            // (0,5)、(2,7)、(6,8)、(9,11)、(10,15)、(12,17)、(16,18)、(19,21)
            //   ↑
            //   i (✔)
            //          ↑
            //          j
            //                 ↑
            //                 j (✔)
            //
            // (9, 11) 这个节目看不了，因为结束时间 11 点 > 第一个节目的开始时间 0 (10) 点
            // ==============================================================

            // ==============================================================
            // (0,5)、(2,7)、(6,8)、(9,11)、(10,15)、(12,17)、(16,18)、(19,21)
            //         ↑
            //         i (✔)
            //                ↑
            //                j
            //                       ↑
            //                       j (✔)
            // ==============================================================

            // ==============================================================
            // (0,5)、(2,7)、(6,8)、(9,11)、(10,15)、(12,17)、(16,18)、(19,21)
            //                ↑
            //                i (✔)
            //                       ↑
            //                       j (✔)
            //                               ↑
            //                               j
            //
            // (12, 17) 这个节目看不了，因为结束时间 17 点 > 第一个节目的开始时间 6 (16) 点
            // ==============================================================

            // ==============================================================
            // (0,5)、(2,7)、(6,8)、(9,11)、(10,15)、(12,17)、(16,18)、(19,21)
            //                       ↑
            //                       i (✔)
            //                               ↑
            //                               j
            //                                        ↑
            //                                        j (✔)
            //                                                 ↑
            //                                                 j
            //
            // (19, 21) 这个节目看不了，因为结束时间 21 点 > 第一个节目的开始时间 9 (19) 点
            // ==============================================================

            for (int j = i; circleIntervals[j].end <= maximumEnd; j++) {
                if (circleIntervals[j].start >= lastEnd) {
                    ans++;
                    lastEnd = circleIntervals[j].end;
                }
            }

            res = Math.max(ans, res);

        }

        return res;
    }

    /**
     * (0,5)
     * (2,7)
     * (6,8)
     * (9,1) // 跨区间了 9 点看到第二天 1 点
     *
     *                       修复
     *                        ↓
     * (0,5)、(2,7)、(6,8)、(9,11)、(10,15)、(12,17)、(16,18)、(19,21)
     *                                ↑       ↑        ↑        ↑
     *                               拷贝    拷贝      拷贝      拷贝
     *
     * @param intervals
     * @param M
     * @return
     */
    private Interval[] copyAndAppend(Interval[] intervals, int M) {
        int N = intervals.length;

        Interval[] total = new Interval[N * 2];
        System.arraycopy(intervals, 0, total, 0, N);

        for (int i = 0; i < N; i++) {
            int start = intervals[i].start;
            int end = intervals[i].end;

            if (end < start) { // 开始时间第一天 9 点，结束时间是第二天 1 点 (9, 1)
                intervals[i].end = end + M; // 修复这个结束时间
                end = intervals[i].end;
            }

            total[i + N] = new Interval(start + M, end + M);
        }

        return total;
    }

}
